package formal.tree.bst;

import java.util.ArrayList;
import java.util.List;

/**
 * @author DengYuan2
 * @create 2021-01-25 22:01
 */
public class E_530 {
    public static void main(String[] args) {
//        Integer[] a= {1,null,3,2,null};
        Integer[] a = {5, 3, 6, 2, 4, null, 7};
        TreeNode treeNode = TreeNode.generateTree(a);
        int res = getMinimumDifference2(treeNode);
        System.out.println(res);
    }

    /**
     * 我的写法-中序遍历-放到数组中-比较相邻节点的绝对差值
     * 类似于E_653
     * 很慢
     * @param root
     * @return
     */
    public static int getMinimumDifference(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inOrder(root,list);
        int length =list.size();
        int min = Math.abs(list.get(0)-list.get(length-1));
        for (int i = 0; i < list.size() - 1; i++) {
            int val = Math.abs(list.get(i)-list.get(i+1));
            if (val<min){
                min = val;
            }
        }
        return min;
    }

    public static void inOrder(TreeNode root, List<Integer> list){
        if (root==null){
            return;
        }
        inOrder(root.left,list);
        list.add(root.val);
        inOrder(root.right,list);
    }

    /**
     * 大神的写法-直接利用中序遍历啊
     * @param root
     * @return
     */
    public static TreeNode pre = null;
    public static int min=Integer.MAX_VALUE;
    public static int getMinimumDifference2(TreeNode root) {
        inOrderSearch(root);
        return min;
    }

    public static void inOrderSearch(TreeNode node){
        if (node==null){
            return;
        }
        inOrderSearch(node.left);
        if (pre!=null){
            min=Math.min(min,Math.abs(pre.val-node.val));
        }
        pre=node;
        inOrderSearch(node.right);
    }


}
